Strom (graf)

Strom

V teorii grafů se jako strom označuje graf, který je souvislý a neobsahuje žádnou kružnici. Lze jej ovšem definovat i dalšími způsoby:

Následující podmínky pro neorientovaný graf G jsou ekvivalentní:

  1. G je strom.
  2. Každé dva vrcholy z G jsou spojeny právě jednou cestou (jednoznačnost cesty).
  3. G je souvislý a po odebrání libovolné hrany se stane nesouvislým (minimální souvislost).
  4. G neobsahuje kružnici, ale po přidání libovolné hrany vznikne v G kružnice (maximální graf bez kružnic) .
  5. G je souvislý a , kde V je množina vrcholů a E množina hran grafu G.

Stromy mohou být:

  • neorientované
  • orientované (kořenové)

Developed by StudentB